#include<stdio.h>

/*
* Temporary variable for KMP algorithm
*/
char T[50];


int main(){
	printf("%s", "this is a test");
}


/*
* Read the lattice and store the strings in a multidimensional array
* input - filename of the lattice
* output - load the input 
*/
void readLattice (char filename[], char ***lattice)
{   
   FILE *file = fopen ( filename, "r" );
   if ( file != NULL )
   {
      char line [ 128 ]; /* or other suitable maximum line size */
 
      while ( fgets ( line, sizeof line, file ) != NULL ) /* read a line */
      {
         fputs ( line, stdout ); /* write the line */
      }
      fclose ( file );
   }
   else
   {
      perror ( filename ); /* why didn't the file open? */
   }
   return 0;
}


/* Checks whether a given pattern is present in the 
*
*/

int checkPatternX(char pattern[], char ***lattice){

}

/*
* Implementation of Knuth Morris Pratt Algorithm
* Inspired from http://www.daniweb.com/software-development/c/threads/83793
* Input 
*    *ptr_i = Pointer to the start of the word to be found
*    *ptr_m = Pointer to the start of the sentence which needs to be checked 
*    word_length = length of the word
*    sentence_length = length of the entire sentence
*/

kmp(char *ptr_i,char *ptr_m,int word_length,int sentence_length)
{
  int pos,m=0,i=0;
  for(;m<sentence_length; )
    {
      if(*(ptr_i+i) == *(ptr_m+m+i))
        {
          i=i+1;
			if(i==word_length)
			 {
			   pos=m+1;
			   printf("The word was found at position %d\n",pos );
			 }
        }
       else
        { 
			 m=m+i-T[i];
			 if(i>0)
				i=T[i]; 
        }
    } 
      return sentence_length;
}

/*
* Knuth Morris Pratt Algorithm initialization step
* Inspired from http://www.daniweb.com/software-development/c/threads/83793
* Input 
*    *ptr_i = Pointer to the start of the word to be found
*    *ptr_m = Pointer to the start of the sentence which needs to be checked 
*    word_length = length of the word
*    sentence_length = length of the entire sentence
*/
 
 
kmp_table(char *ptr_i,char *ptr_m,int word_length,int sentence_length)
{
	 int i,j;
	  i=2;
	  j=0;
	  T[0]=-1;
	  T[1]=0;
	  for(;i<word_length; )
	  {
			if(*(ptr_i+i-1) == *(ptr_i+j))
			   {
				T[i]=j+1;
				i=i+1;
				j=j+1;
			   }
	 
			else if(j>0)
				{
				 j=T[j];
				}
	 
			else
				{
				 T[i]=0;
				 i=i+1;
				}
	 } 
}